<?php
/**
 * @title 111. 二叉树的最小深度 - 层次遍历
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
        /**
         * @since 2020-08-21 空二叉树
         */
        if($root === null){
            return 0;
        } else {}

        /**
         * @since 2020-08-21 深度
         */
        $depth = 0;

        /**
         * @since 2020-08-21 层次遍历
         */
        $nexts = [$root];
        while($nexts){
            $nextsTmp = [];
            $depth++;

            /**
             * @since 2020-08-21 逐个节点检查, 是否叶子节点
             */
            foreach ($nexts as $node){
                /**
                 * @since 2020-08-21 叶子节点
                 */
                if($node->left === null AND $node->right === null){
                    $nextsTmp = [];
                    break;
                } elseif($node->left !== null){
                    /**
                     * @since 2020-08-21 左子树
                     */
                    $nextsTmp[] = $node->left;

                    /**
                     * @since 2020-08-21 右子树
                     */
                    if($node->right !== null){
                        $nextsTmp[] = $node->right;
                    }
                } else {
                    /**
                     * @since 2020-08-21 左子树为null, 右子树一定存在
                     */
                    $nextsTmp[] = $node->right;
                }
            }

            /**
             * @since 2020-08-21 下次循环
             */
            $nexts = $nextsTmp;
        }

        /**
         * @return
         */
        return $depth;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.21.php
 */
$datas = [
    [3,9,20,null,null,15,7],
    null,
    [3,9,20],
    [3],
    [1,2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minDepth($xhprof->tree($data));
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}
$xhprof->end();
